A. Field of the Invention
The present invention relates generally to data processing and, more particularly, to reordering of information that arrives out of order after transmission.
B. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was turned on.
To meet the new demands, purpose-built routers were designed. Purpose-built routers are designed and built with components optimized for routing. They not only handled higher line rates and higher network traffic volume, they also added functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A switching fabric or other transmission medium may be implemented in the router to carry the packets between the ports. In a high-performance purpose-built router, the switching fabric may transmit a large amount of information between a number of internal components. Typically, the information is transmitted in discrete quantities called packets, or broken down even further into a series of cells.
One property of the switching fabric is that, even though it may have enough bandwidth to handle its cell traffic, cells transmitted to a particular destination may arrive at that destination out of order. Thus, although a first cell may be transmitted before a second cell, the second cell may be received before the first cell. Generally, the order of the received cells is important and should be preserved.
Reorder circuits may be used to reorder cells received from a particular source into their correct transmission order. Essentially, each cell, as it is transmitted from a source, is appended with a sequence number. The reorder circuits examine the received sequence numbers to determine the correct cell order.
One implementation of a reorder circuit is as a circular buffer in which arriving cells are placed at positions in the buffer based on the cell's sequence number. A pointer register keeps track of the rear-most position in the buffer. When a cell arrives that corresponds to the position in the pointer register, the reorder circuit increments the pointer value to point to the next open position in the buffer and processes all cells between the old pointer position and the new pointer position.
Typically, out-of-order cells are received in a relatively close sequence to their true order. Occasionally, however, a cell may arrive that is significantly out-of-order (e.g., the cell is delayed much more than normal). Designing a reorder circuit to be able to reorder such pathological worst case conditions can significantly increase the memory size requirements of the reorder circuit.
Thus, there is a need in the art for reorder circuits to be able to effectively handle worst case out-of-order scenarios.